import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


ArrayList<Integer> cardCompare(String card1, String card2) {
    // Define an array of strings containing all possible suit representations.
    String[] suits = {"H", "C", "D", "S"};
    // Extract the suit part of 'card1' (the last character) and find its index in the'suits' array.
    int suit1 = Arrays.asList(suits).indexOf(card1.substring(card1.length() - 1));
    // Do the same for 'card2' to get its suit's index and priority.
    int suit2 = Arrays.asList(suits).indexOf(card2.substring(card2.length() - 1));

    // Check if the suit of 'card1' has a lower priority (lower index) than the suit of 'card2'.
    if (suit1 < suit2) {
        return new ArrayList<>(List.of(-1));
    }
    // Check if the suit of 'card1' has a higher priority (higher index) than the suit of 'card2'.
    else if (suit1 > suit2) {
        return new ArrayList<>(List.of(1));
    }
    // If the suits of both cards are equal, proceed to compare the numbers on the cards.
    else {
        // Parse the number part of 'card1' (the substring before the suit character) as an integer.
        int num1 = Integer.parseInt(card1.substring(0, card1.length() - 1));
        // Parse the number part of 'card2' (the substring before the suit character) as an integer.
        int num2 = Integer.parseInt(card2.substring(0, card2.length() - 1));

        // If the number on 'card1' is less than the number on 'card2', return an ArrayList with -1 to show that 'card1' is smaller.
        if (num1 < num2) {
            return new ArrayList<>(List.of(-1));
        }
        // If the number on 'card1' is greater than the number on 'card2', return an ArrayList with 1 to indicate that 'card1' is larger.
        else if (num1 > num2) {
            return new ArrayList<>(List.of(1));
        }
        // If the numbers on both cards are equal, return an ArrayList with 0 to denote that the two cards are equal.
        else {
            return new ArrayList<>(List.of(0));
        }
    }
}


ArrayList<String> bubbleSort(ArrayList<String> array) {
    // Get the size of the input ArrayList. This determines how many passes through the list are needed for sorting.
    int n = array.size();
    // With each pass, one more element gets sorted into its correct position at the end of the list.
    for (int i = 0; i < n - 1; i++) {
        // Inner loop that compares adjacent elements in the list.
        for (int j = 0; j < n - i - 1; j++) {
            // Use the 'cardCompare' method to compare two adjacent cards in the list.
            if (cardCompare(array.get(j), array.get(j + 1)).get(0) > 0) {
                // Create a temporary variable to hold one of the elements during the swap process.
                String temp = array.get(j);
                // Swap the current element with the next element.
                array.set(j, array.get(j + 1));
                array.set(j + 1, temp);
            }
        }
    }
    // Return the sorted ArrayList of card strings.
    return array;
}


ArrayList<String> mergeSort(ArrayList<String> array) {
    // If the size of the input ArrayList is 1 or less, it means the list is already sorted (a single element is considered sorted by itself).
    if (array.size() <= 1) {
        return array;
    }

    // Calculate the middle index of the list to divide it evenly (or as evenly as possible) into two halves.
    int mid = array.size() / 2;
    // Create a new ArrayList containing the left half of the original list.
    ArrayList<String> left = new ArrayList<String>(array.subList(0, mid));
    // Create a new ArrayList containing the right half of the original list.
    ArrayList<String> right = new ArrayList<String>(array.subList(mid, array.size()));

    // Recursively call the'mergeSort' method on the left half of the list to sort it.
    left = mergeSort(left);
    // Recursively call the'mergeSort' method on the right half of the list to sort it.
    right = mergeSort(right);

    // Merge the sorted left and right halves and return the resulting sorted list.
    return merge(left, right);
}


ArrayList<String> merge(ArrayList<String> left, ArrayList<String> right) {
    // Create an empty ArrayList to store the merged and sorted result.
    ArrayList<String> result = new ArrayList<String>();
    int i = 0, j = 0;

    // While there are still elements remaining in both the left and right lists, compare the current elements from each list.
    while (i < left.size() && j < right.size()) {
        // Use the 'cardCompare' method to compare the current cards from the left and right lists.
        if (cardCompare(left.get(i), right.get(j)).get(0) <= 0) {
            result.add(left.get(i));
            i++;
        }
        // Otherwise, if the card from the right list is smaller, add the card from the right list to the result list and move to the next element in the right list.
        else {
            result.add(right.get(j));
            j++;
        }
    }

    // Add any remaining elements from the left list to the result list (if there are any).
    result.addAll(left.subList(i, left.size()));
    // Add any remaining elements from the right list to the result list (if there are any).
    result.addAll(right.subList(j, right.size()));

    // Return the merged and sorted ArrayList of card strings.
    return result;
}


long measureBubbleSort(String filename) throws IOException {
    // Create an ArrayList to store the card strings read from the file.
    ArrayList<String> list = new ArrayList<String>();
    // Create a BufferedReader object to read the contents of the file line by line.
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    String line;

    // Read each line from the file, trim any leading or trailing whitespace, and add it to the ArrayList as a card string.
    while ((line = reader.readLine())!= null) {
        list.add(line.trim());
    }
    // Close the BufferedReader to release associated resources.
    reader.close();

    // Record the start time of the sorting process in milliseconds using the current system time.
    long startTime = System.currentTimeMillis();

    // Call the 'bubbleSort' method to sort the list of cards.
    bubbleSort(list);

    // Record the end time of the sorting process in milliseconds using the current system time.
    long endTime = System.currentTimeMillis();

    // Calculate and return the elapsed time by subtracting the start time from the end time.
    return endTime - startTime;
}


long measureMergeSort(String filename) throws IOException {
    // Create an ArrayList to store the card strings read from the file.
    ArrayList<String> list = new ArrayList<String>();
    // Create a BufferedReader object to read the contents of the file line by line.
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    String line;

    // Read each line from the file, trim any leading or trailing whitespace, and add it to the ArrayList as a card string.
    while ((line = reader.readLine())!= null) {
        list.add(line.trim());
    }
    // Close the BufferedReader to release associated resources.
    reader.close();

    // Record the start time of the sorting process in milliseconds using the current system time.
    long startTime = System.currentTimeMillis();

    // Call the'mergeSort' method to sort the list of cards.
    mergeSort(list);

    // Record the end time of the sorting process in milliseconds using the current system time.
    long endTime = System.currentTimeMillis();

    // Calculate and return the elapsed time by subtracting the start time from the end time.
    return endTime - startTime;
}


void sortComparison(String[] filenames) throws IOException {
    // Create a FileWriter object to write data to the "sortComparison.csv" file.
    FileWriter writer = new FileWriter("sortComparison.csv");
    // Create a BufferedWriter object to improve the efficiency of writing to the file and wrap it around the FileWriter.
    BufferedWriter bufferedWriter = new BufferedWriter(writer);

    bufferedWriter.write(", ");
    for (String filename : filenames) {
        BufferedReader br = new BufferedReader(new FileReader(filename));
        int lineCount = 0;
        while (br.readLine()!= null) {
            lineCount++;
        }
        br.close();
        bufferedWriter.write(lineCount + ", ");
    }
    bufferedWriter.newLine();

    bufferedWriter.write("bubbleSort, ");
    for (String filename : filenames) {
        // Call the'measureBubbleSort' method to measure the time taken by Bubble Sort on the current file.
        long bubbleTime = measureBubbleSort(filename);
        bufferedWriter.write(bubbleTime + ", ");
    }
    bufferedWriter.newLine();

    bufferedWriter.write("mergeSort, ");
    for (String filename : filenames) {
        // Call the'measureMergeSort' method to measure the time taken by Merge Sort on the current file.
        long mergeTime = measureMergeSort(filename);
        bufferedWriter.write(mergeTime + ", ");
    }
    bufferedWriter.newLine();

    bufferedWriter.close();
}